#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <fstream>

class ACautomation {
	struct Trie {
		std::vector<int> exist;
		Trie* fail = nullptr;
		std::unordered_map<char, Trie*> child;
	};
	Trie* root = new Trie;
private:
	void buildTrie(std::string word) {
		Trie* node = root;
		for (int i = 0; i < word.size(); ++i) {
			if (node->child[word[i]] == nullptr) node->child[word[i]] = new Trie;
			node = node->child[word[i]];
		}
		node->exist.push_back(word.size());
	}
	void getFail() {
		std::queue<Trie*> q;
		root->fail = root;
		for (auto& it : root->child) {
			q.emplace(it.second);
			it.second->fail = root;
		}
		while (!q.empty()) {
			Trie* node = q.front();
			q.pop();
			for (auto& it : node->child) {
				q.emplace(it.second);
				if (node->fail->child[it.first] == nullptr) it.second->fail = root;
				else it.second->fail = node->fail->child[it.first];
			}
		}
	}
public:
	ACautomation(std::vector<std::string> words) {
		for (auto& word : words) {
			buildTrie(word);
		}
		getFail();
	}
	Trie* current = root;
	bool StreamChecker(char letter) {
		if (current->child[letter] == nullptr) 
			current = root;
		else current = current->child[letter];
		return current->exist.empty() ? 0 : current->exist[0];
	}

	std::string sheld(std::string s) {
		Trie* node = root;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == ' ') continue;
			if (node->child[s[i]] == nullptr) node = root;
			if (node->child[s[i]]) node = node->child[s[i]];
			int n = node->exist.empty() ? 0 : node->exist[0];
			if (n == 0) continue;
			for (int j = i - n + 1; j <= i; ++j) {
				s[j] = '*';
			}
		}
		return s;
	}
};

int main() {
	//std::ifstream ifs("words.dat", std::ios::in);
	std::vector<std::string> words = { "fuck", "bitch", "fuxk", "lust", "nipple", "妈", "草", "屎", "厕所"};
	ACautomation* ac = new ACautomation(words);
	std::string s = "李白，你妈没了 这边建议厕所里的屎吃多点";
	//for (auto i : s) {
	//	std::cout << ac->StreamChecker(i) << " ";
	//}
	std::cout << ac->sheld(s);
	return 0;
}